package algorithm;

import util.GsonUtil;

import java.util.LinkedList;
import java.util.List;
import java.util.concurrent.TimeUnit;

/**
 * 数字相关算法
 * 包括：
 * 求 Fibonacci 数列
 * 求质数 埃氏筛选法
 *
 * @Author Antony
 * @Since 2018/6/27 10:58
 */
public class NumberAlgorithm {

    public static void main(String[] args) {
        // 求前10个 Fibonacci 数
        int[] fib = fibonacci(10);
        System.out.println(GsonUtil.toJson(fib));


//        int num = 10;
//        int num = 20;
        int num = 40;
        long t1 = System.nanoTime();
        System.out.println(fib(num));           // fib递归
        long t2 = System.nanoTime();
        System.out.println(fibOptimize(num));   // fib优化
        long t3 = System.nanoTime();

        System.out.println(String.format("fib用递归运行时间：%s ns",t2-t1));
        System.out.println(String.format("fib优化后运行时间：%s ns",t3-t2));



        int count = 20;     // 求前20个质数
//        System.out.println(primeNumber(count));

        int limit = 100;    // 求100以内的质数
//        System.out.println(primeNumberLimit(limit));
    }


    /**
     * 求第n个fibonacci数。使用递归的方式
     * 但是这里有个缺陷, 每次递归都会重复计算，性能很差。
     * @param n
     * @return
     */
    public static int fib(int n){
        if(n<=0) return 0;
        if(n>=2){
            return fib(n-1) + fib(n-2);
        }else{
            return n;
        }
    }

    public static int fibOptimize(int n){
        if(n<=0) return 0;
        int pre=0, curr=1, tmp=0;
        while(n>1){
            tmp = pre;
            pre = curr;
            curr = curr + tmp;
            n--;
        }

        return curr;
    }

    /**
     * 返回指定个数的 Fibonacci 数
     */
    public static int[] fibonacci(int count){
        int[] result = new int[count];
        int pre = 0;
        int current = 1;
        int temp;
        for(int i=0; i<count; i++){
            result[i] = current;
            temp = pre;
            pre = current;
            current = current + temp;
        }
        return result;
    }



    //求前 limitNumber 之内，所有的质数
    public static List<Integer> primeNumberLimit(int limitNumber){
        if(limitNumber < 1){
            throw new IllegalArgumentException("for Input math:"+limitNumber);
        }
        List<Integer> result = new LinkedList<>();
        if(limitNumber == 1){
            result.add(1);
            return result;
        }

        result.add(2);
        if(limitNumber == 2){
            return result;
        }

        int number = 3;
        while (number < limitNumber){
            boolean isPrime = true;
            for (Integer p : result){
                if(number % p == 0){
                    isPrime = false;
                    break;
                }
            }

            if(isPrime){
                result.add(number);
            }

            number +=2;
        }

        //把1 添加到第一个元素
        result.add(0,1);

        return result;
    }

    //求从1开始 primeCount数量的质数
    public static List<Integer> primeNumber(int primeCount){
        if(primeCount <=0){
            throw new IllegalArgumentException("count must greater than 0");
        }
        List<Integer> list = new LinkedList<>();
        if(primeCount == 1){
            list.add(1);
            return list;
        }

        if(primeCount == 2){
            list.add(1);
            list.add(2);
            return list;
        }

        //从3开始，只算奇数。可以减少计算次数
        int count = 2;
        int number = 3;
        list.add(2);
        while(count < primeCount){
            boolean isPrime = true;
            for(Integer i : list){
                if(i!= 1 && number % i == 0){
                    isPrime = false;
                    break;
                }
            }

            if(isPrime){
                list.add(number);
                count++;
            }

            number +=2;
        }

        list.add(0,1);
        return list;
    }
}
